"""
Problem 26: https://projecteuler.net/problem=26

A unit fraction contains 1 in the numerator. The decimal representation of the
unit fractions with denominators 2 to 10 are given:

1/2	= 	0.5
1/3	= 	0.(3)
1/4	= 	0.25
1/5	= 	0.2
1/6	= 	0.1(6)
1/7	= 	0.(142857)
1/8	= 	0.125
1/9	= 	0.(1)
1/10	= 	0.1
Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be
seen that 1/7 has a 6-digit recurring cycle.

Find the value of d < 1000 for which 1/d contains the longest recurring cycle
in its decimal fraction part.
"""

# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = Thonny Python3.8.3
@creat_time = 2022/5/10
'''


def recurringCycle(d: int) -> int:
    '''
    >>> print(recurringCycle(2))
    0
    >>> print(recurringCycle(3))
    1
    >>> print(recurringCycle(7))
    6
    >>> print(recurringCycle(499))
    12
    '''

    dividend = 10 ** len(str(d))

    res = []

    while True:
        x, dividend = divmod(dividend, d)
        dividend = dividend * 10

        if dividend == 0:
            # print(d, ', not cycle',res)
            return 0

        if x in res and x != 0:  # such as 1200/9999, allow repeat 0, else return
            # print(d, ', exist cycle',res)
            return len(res) - res.index(x)

        res.append(x)


def solution(limit: int = 1000) -> int:
    '''

    Find the value of d < 1000 for 
    which 1/d contains the longest recurring cycle

    >>> print(solution(10))
    (7, 6)
    >>> print(solution(5))
    (3, 1)
    '''

    cycle = 0
    res = 1

    for d in range(2, limit):
        rc = recurringCycle(d)
        if rc > cycle:
            cycle = rc
            res = d

    return res, cycle


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)

    print(solution())
    # (499, 12)
